package Top200;

/**
 * @author zhangmin
 * @create 2022-02-21 16:48
 * 回溯
 */
public class solveSudoku37 {
    //路径：已经选择好的位置
    //选择列表：1-9中符合条件的
    //终止条件：当i，j到最后
    boolean backtrack(char[][] board,int i,int j){
        if (j==9){
            return backtrack(board,i+1,0);
        }
        if (i==9){
            return true;
        }
        if (board[i][j]!='.'){
            return backtrack(board,i,j+1);
        }
        for (char k = '1'; k <= '9'; k++) {
            if (!isValid(board,i,j,k)) continue;
            board[i][j]=k;
            if (backtrack(board,i,j+1)){
                return true;
            }
            board[i][j]='.';
        }
        return false;
    }
    boolean isValid(char[][] board,int i,int j,char c){
        for (int k = 0; k < 9; k++) {
            if (board[i][k]==c) return false;
            if (board[k][j]==c) return false;
            if (board[(i/3)*3+k/3][(j/3)*3+k%3]==c) return false;
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
}
